COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	 Programs for testing 3n+1 problem hypotheses - perhaps obviating
C00004 ENDMK
C⊗;
;;; Programs for testing 3n+1 problem hypotheses - perhaps obviating
;;; excuse for 3n+1 chip.

;;; table(k) for k a small integer is a list of the 2↑k triples,
;;; (i z x) where i ranges from 0 to 2↑k -1, z is the pattern
;;; of (3n+1)/2 and n/2 that are executed in k steps of the algorithm
;;; starting with i, and x is the value of u after the k steps.
;;;
;;; Here phi(u) = if even u then u/2 else (3u+1)/2,  Curiously,
;;; the map n → z often take n to n and otherwise executes a small
;;; cycle whose length is a power of 2.

(defun table (k)
       (prog (z x w)
	     (setq z nil)
	     (setq m (sub1 (expt 2 k)))
	     (do
	      ((i 0 (add1 i)))
	      ((> i m))
	      (setq x i)
	      (setq w nil)
	      (do
	       ((j 0 (add1 j)))
	       ((> j (sub1 k)))
	       (if
		(equal 0 (remainder x 2))
		(prog ()
		      (setq w (cons 0  w))
		      (setq x (quotient x 2)))
		(prog ()
		      (setq w (cons 1 w))
		      (setq x (quotient (add1 (times 3 x)) 2)))))
	      (setq z (cons (list i (foo w 0) x) z)))
	     (return (reverse z))))

(defun foo (w n) (if (null w) n (foo (cdr w) (plus n n (car w)))))